Masala #0318
So’rovlarni tartiblash 2
Sizga N uzunlikdagi A massivi berilgan. Massiv ustida bajarish uchun Q ta so’rov berilgan. Har bir so’rov quyidagilardan biri bo’lishi mumkin:
- L R X : Massivning [L, R] indekslari oralig’idagi barcha elementga X sonini qo’shish
- L R X : Massivning [L, R] indekslari oralig’idagi barcha elementni qiymatini X ga almashtirish
Berilgan barcha so’rovlar massiv ustida bajarilishi kerak.
Sizga so’rovlarning bajarilish tartibini o’zgartirishga ruxsat etiladi. So’rovlar oxirida A massivning hosil qilish mumkin bo’lgan leksikografik eng katta qiymatini aniqlang.
Kirish faylining dastlabki satrida ikkita butun son, N(1 ≤ N ≤ 105) va Q(1 ≤ Q ≤ 105) kiritiladi.
Ikkinchi satrda N ta butun son, A(-105 ≤ Ai ≤ 105) massiv elementlari kiritiladi.
Keyingi qatordan boshlab Q ta qatorda 4 tadan butun son, so’rov turi({1,2}), L, R(1 ≤ L ≤ R ≤ N), X(-105 ≤ X ≤ 105) kiritiladi.
Chiqish faylining yagona satrida N ta butun son, A massiv ustida barcha so’rovlarni bajargandan so’ng hosil qilish mumkin bo’lgan leksikografik eng katta massivni chop eting.
# | input.txt | output.txt |
---|---|---|
1 |
5 3 1 2 3 4 5 1 3 4 2 2 1 2 3 1 4 5 -6 |
3 3 5 0 -1 |